package com.dataStructures.sort;

import java.util.Arrays;

/**
 * 归并排序 时间复杂度 O(nlogn)
 */
public class MergeSort {
	public static void main(String[] args) {
		int[] arr = {8, 9, 1, 7, 2, 3, 5, 4, 6, 0};
		System.out.println("排序前：" + Arrays.toString(arr));
		mergeSort(arr, 0, arr.length - 1, new int[arr.length]);
		System.out.println("排序后：" + Arrays.toString(arr));

		// 批量测试
		int[] arrBatch = new int[10000000];
		for (int i = 0; i < 10000000; i++) {
			arrBatch[i] = (int) (Math.random() * 10000000);
		}
		long begin = System.currentTimeMillis();
		mergeSort(arrBatch, 0, arrBatch.length - 1, new int[arrBatch.length]);
		System.out.println("coast time:" + (System.currentTimeMillis() - begin));
	}

	public static void mergeSort(int[] arr, int left, int right, int[] temp) {
		if (left < right) {
			int mid = (left + right) / 2;
			// 向左递归分解
			mergeSort(arr, left, mid, temp);

			// 向右递归分解
			mergeSort(arr, mid + 1, right, temp);

			// 合并
			merge(arr, left, right, mid, temp);
		}
	}

	/**
	 * 合并
	 *
	 * @param arr   原始数组
	 * @param left  左边有序序列的初始索引
	 * @param right 右边有序序列的初始索引
	 * @param mid   中间索引
	 * @param temp  中转数组
	 */
	public static void merge(int[] arr, int left, int right, int mid, int[] temp) {
		int i = left;
		int j = mid + 1;
		// 指向 temp 数组的当前索引
		int t = 0;


		//(一) 先把左右两边(有序)的数据按照规则填充到 temp 数组，直到左右两边的有序序列，有一边处理完毕为止
		while (i <= mid && j <= right) {
			if (arr[i] <= arr[j]) {
				temp[t++] = arr[i++];
			} else {
				temp[t++] = arr[j++];
			}
		}

		//(二) 把有剩余数据的一边的数据依次全部填充到 temp
		while (i <= mid) {
			temp[t++] = arr[i++];
		}
		while (j <= right) {
			temp[t++] = arr[j++];
		}

		//(三) 将 temp 数组的元素拷贝到 arr（注意，并不是每次都拷贝所有）
		t = 0;
		int tempLeft = left;
		while (tempLeft <= right) {
			arr[tempLeft++] = temp[t++];
		}
	}
}
